{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "531a62c1-bfca-4ce6-8a2b-651190dbeb6a",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/ugly-number-ii/\n",
    "\n",
    "\n",
    "Success \n",
    "\n",
    "___\n",
    "\n",
    "\n",
    "> Sometimes, you think you gonna use methodA to solve a problem, but in the end, you may found you are using a totally different method to solve the problem. So don't be afraid, just do it.\n",
    "\n",
    "___\n",
    "\n",
    "\n",
    "Beats\n",
    "98.39%\n",
    "\n",
    "___\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    ugly_numbers = []\n",
    "    def __init__(self):\n",
    "        self.generate_ugly_numbers()\n",
    "\n",
    "    def generate_ugly_numbers(self):\n",
    "        n = 1690 * 8\n",
    "        if len(self.ugly_numbers) == 0:\n",
    "            i = 1\n",
    "            ugly_numbers = [1]\n",
    "            levels = [[1]]\n",
    "            \n",
    "            while n >= i:\n",
    "                temp = []\n",
    "                for one in levels[-1]:\n",
    "                    for num in [2,3,5]:\n",
    "                        new_num = num*one\n",
    "                        if new_num not in temp:\n",
    "                            ugly_numbers.append(new_num)\n",
    "                            temp.append(new_num)\n",
    "                        i += 1\n",
    "                levels.append(temp)\n",
    "                \n",
    "            ugly_numbers.sort()\n",
    "            self.ugly_numbers = ugly_numbers\n",
    "\n",
    "        #self.ugly_numbers = [] # yingshaoxo: if the above code isn't work, that is because the stupid leetcode has used two system to do the test, it's working fine with the `Run` button; what you could do is to generate the whole ugly_number list, then hard code it here.\n",
    "\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        #2023/01/17 05:50\n",
    "        \n",
    "        return self.ugly_numbers[n-1]\n",
    "\n",
    "        #2023/01/17 09:08\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97ae7414-e8d9-4d18-a617-41f04b62ca45",
   "metadata": {},
   "source": [
    "# Experiment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e9f0bee0-9935-466a-bc0b-00a2780321c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(maxsize = None)\n",
    "    def isUgly(self, n: int) -> bool:\n",
    "        #6:27\n",
    "        @lru_cache(maxsize = None)\n",
    "        def divition(n):\n",
    "            #print(n)\n",
    "            if n == 0:\n",
    "                return False\n",
    "            if int(n) - n != 0:\n",
    "                return False\n",
    "            if n in [1,2,3,5]:\n",
    "                return True\n",
    "            else:\n",
    "                return any([divition(n/2), divition(n/3), divition(n/5)])\n",
    "        return divition(n) \n",
    "\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        #2023/01/17 05:50\n",
    "        result = []\n",
    "        i = 0\n",
    "        while True:\n",
    "            i += 1\n",
    "            if (self.isUgly(i)):\n",
    "                result.append(i)\n",
    "            if len(result) >= n:\n",
    "                result = result[:n]\n",
    "                break\n",
    "        print(result)\n",
    "        return result[-1]\n",
    "        #2023/01/17 05:59"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9b46fc20-02c4-4cc5-baa4-db56a4888950",
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "Cell \u001b[0;32mIn [7], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mSolution\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mnthUglyNumber\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m1690\u001b[39;49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[0;32mIn [6], line 26\u001b[0m, in \u001b[0;36mSolution.nthUglyNumber\u001b[0;34m(self, n)\u001b[0m\n\u001b[1;32m     24\u001b[0m \u001b[38;5;28;01mwhile\u001b[39;00m \u001b[38;5;28;01mTrue\u001b[39;00m:\n\u001b[1;32m     25\u001b[0m     i \u001b[38;5;241m+\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[38;5;241m1\u001b[39m\n\u001b[0;32m---> 26\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m (\u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43misUgly\u001b[49m\u001b[43m(\u001b[49m\u001b[43mi\u001b[49m\u001b[43m)\u001b[49m):\n\u001b[1;32m     27\u001b[0m         result\u001b[38;5;241m.\u001b[39mappend(i)\n\u001b[1;32m     28\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28mlen\u001b[39m(result) \u001b[38;5;241m>\u001b[39m\u001b[38;5;241m=\u001b[39m n:\n",
      "Cell \u001b[0;32mIn [6], line 18\u001b[0m, in \u001b[0;36mSolution.isUgly\u001b[0;34m(self, n)\u001b[0m\n\u001b[1;32m     16\u001b[0m     \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[1;32m     17\u001b[0m         \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28many\u001b[39m([divition(n\u001b[38;5;241m/\u001b[39m\u001b[38;5;241m2\u001b[39m), divition(n\u001b[38;5;241m/\u001b[39m\u001b[38;5;241m3\u001b[39m), divition(n\u001b[38;5;241m/\u001b[39m\u001b[38;5;241m5\u001b[39m)])\n\u001b[0;32m---> 18\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43mdivition\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[0;32mIn [6], line 17\u001b[0m, in \u001b[0;36mSolution.isUgly.<locals>.divition\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m     15\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;01mTrue\u001b[39;00m\n\u001b[1;32m     16\u001b[0m \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[0;32m---> 17\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28many\u001b[39m([\u001b[43mdivition\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[38;5;241;43m/\u001b[39;49m\u001b[38;5;241;43m2\u001b[39;49m\u001b[43m)\u001b[49m, divition(n\u001b[38;5;241m/\u001b[39m\u001b[38;5;241m3\u001b[39m), divition(n\u001b[38;5;241m/\u001b[39m\u001b[38;5;241m5\u001b[39m)])\n",
      "Cell \u001b[0;32mIn [6], line 14\u001b[0m, in \u001b[0;36mSolution.isUgly.<locals>.divition\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m     12\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28mint\u001b[39m(n) \u001b[38;5;241m-\u001b[39m n \u001b[38;5;241m!=\u001b[39m \u001b[38;5;241m0\u001b[39m:\n\u001b[1;32m     13\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;01mFalse\u001b[39;00m\n\u001b[0;32m---> 14\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m n \u001b[38;5;129;01min\u001b[39;00m [\u001b[38;5;241m1\u001b[39m,\u001b[38;5;241m2\u001b[39m,\u001b[38;5;241m3\u001b[39m,\u001b[38;5;241m5\u001b[39m]:\n\u001b[1;32m     15\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;01mTrue\u001b[39;00m\n\u001b[1;32m     16\u001b[0m \u001b[38;5;28;01melse\u001b[39;00m:\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "Solution().nthUglyNumber(1690)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "6572dbef-5066-4944-92aa-b6a15b78ff0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pprint import pprint "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "id": "1310bfc2-ee88-4d0b-9215-9f0b5503ee65",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 1690 * 8\n",
    "\n",
    "i = 1\n",
    "ugly_numbers = [1]\n",
    "levels = [[1]]\n",
    "\n",
    "while n >= i:\n",
    "    temp = []\n",
    "    for one in levels[-1]:\n",
    "        for num in [2,3,5]:\n",
    "            new_num = num*one\n",
    "            if new_num not in temp:\n",
    "                ugly_numbers.append(new_num)\n",
    "                temp.append(new_num)\n",
    "            i += 1\n",
    "    #print(temp)\n",
    "    levels.append(temp)\n",
    "\n",
    "#ugly_numbers = list(sorted(set(ugly_numbers)))\n",
    "ugly_numbers.sort()\n",
    "#print(ugly_numbers)\n",
    "#print(ugly_numbers)[:1691]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "7d3f28e9-550c-4d85-88b9-78094638734b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2123366400\n"
     ]
    }
   ],
   "source": [
    "print(ugly_numbers[1690-1])\n",
    "assert ugly_numbers[1690-1] == 2123366400"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "1db0f6c5-a248-44b2-9046-7e2ce0454cde",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3515625"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ugly_numbers[284-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "e431e7bc-63a3-4f6a-87a1-687f3deda323",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Solution()\n",
    "for num in ugly_numbers:\n",
    "    if s.isUgly(num) == False:\n",
    "        print(num)\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "273e510f-d96e-44a0-9220-b6c80ffc8e7b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.isUgly(65536)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "4415aa0f-94c2-446f-9547-872604638d04",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32768.0"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "65536/2 #284"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "ae4e126a-44b1-4977-9cb7-b30def6c8d2b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16384.0"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "32768 / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "e463ea66-032d-44cf-a46d-d64ce5754b8a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8192.0"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "16384/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "f5ca8cdd-5a8b-431d-ac1f-e22d52e394bb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4096.0"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "8192/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "7abf3c09-dc4b-466c-81c0-4f5465708f9d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2048.0"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "4096/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "f4b94616-f44b-4f43-ba94-0d9a948155d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1024.0"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2048/2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "1bfce376-e958-44a5-b4c8-ef4297583289",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "512.0"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1024/2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "f2a6abb5-7d6b-42b2-a469-999bcec99a60",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "256.0"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "512/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "54be9eda-30a5-4da9-8b7d-3c248faa2c67",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6561.0"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "6561/1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "faa36135-5e85-4d96-8d49-ba867f005179",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}